There are systems in which it is desirable to distribute a large database or other information set to multiple users, each user to have access to different subsets of the data. Besides databases, such systems include pay-per-view broadcasts in which each customer has purchased viewing rights to a different set of programs, in-flight entertainment systems, and fingerprinting methodologies wherein multiple copies of each content clip are produced and each recipient is given access to exactly one of the copies of each clip.
One method to enable each user to access the data to which the user is entitled is to separately encrypt each datum and distribute to the user only the keys to the exact subset of data to which the user is entitled. Thus, the problem of distributing different data sets is reduced to the problem of distributing different key sets, each key set being a subset of a universe of keys.
If the universe of keys is large, then the subsets of keys that must be customized and separately sent to each individual user may be large. This can impose substantial burdens on the distribution system.
For example, suppose that each of m customers in a cable television system, on which k pay-per-view shows are to be aired over a given period, is to be given some subset of k keys. If each customer, on average, obtains rights to r of these k shows, then conventional methods would require that a total of mr keys be distributed. There is a point where the number of customers can be so large as to make distribution of the total number (mr) of keys impractical.